package com.java.recursive;

/**
 * 递归解决迷宫问题
 * 迷宫为大小[8][7]的二维数组，如下这样一个形式
 * 设置一个小球从[1][1] 起点开始前进，到达[6][5]位置
 * 规定：1代表不可通过的地方，0代表未走过的地方，2代表可以通过的地方，3表示走过但这条路径不通
 * 策略：小球的前进策略是 下 -> 右 -> 上 -> 左，如果该点的所有方向都走不通，再回溯
 * 游戏结束：当小球到达[6][5], [6][5] = 2，通路找到
 * 1 1 1 1 1 1 1
 * 1 0 0 0 0 0 1
 * 1 0 0 0 0 0 1
 * 1 1 1 0 0 0 1
 * 1 0 0 0 0 0 1
 * 1 0 0 0 0 0 1
 * 1 0 0 0 0 0 1
 * 1 1 1 1 1 1 1
 *
 * @author 19252
 * @date 2020/7/13
 */
public class Labyrinth {
    public static void main(String[] args) {
        // 首先创建一个二维数组模拟迷宫
        int[][] labyrinthMap = new int[8][7];
        int row = labyrinthMap.length;
        int col = labyrinthMap[0].length;

        // 使用1表示墙

        // 上下全部置为1
        for (int i = 0; i < col; i++) {
            labyrinthMap[0][i] = 1;
            labyrinthMap[7][i] = 1;
        }
        // 左右全部置为1
        for (int i = 0; i < row; i++) {
            labyrinthMap[i][0] = 1;
            labyrinthMap[i][6] = 1;
        }
        // 设置相应的挡板在[3][1]和[3][2]两个位置
        labyrinthMap[3][1] = 1;
        labyrinthMap[3][2] = 1;
        // 查看地图输出的效果
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                System.out.print(labyrinthMap[i][j] + " ");
            }
            System.out.println();
        }
        // 使用递归回溯给小球找路
        getWay(labyrinthMap, 1, 1);
        System.out.println("==========> 小球寻路结果 <==========");
        // 查看小球在地图上的寻路路径
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                System.out.print(labyrinthMap[i][j] + " ");
            }
            System.out.println();
        }
    }


    /**
     * 小球寻路方法
     * @param labyrinthMap 小球所走的迷宫
     * @param i 小球的起点 row 的 值
     * @param j 小球的起点 col 的 值
     * @return 返回小球是否可以找到正确的路，true 找到，false未找到
     */
    public static boolean getWay(int[][] labyrinthMap, int i, int j){
        int row = 6;
        int col = 5;
        int numOfWin = 2;
        if (labyrinthMap[row][col] == numOfWin) {
            return true;
        }else {
            // 如果当前的这个点还没有走过
            // 按照策略 下 -> 右 -> 上 -> 左 的方式开始前进
            if (labyrinthMap[i][j] == 0){
                // 先假定这个点是可以走通的
                labyrinthMap[i][j] = 2;
                // 先向下走
                if (getWay(labyrinthMap, i + 1, j)){
                    return true;
                }
                // 再向右走
                else if (getWay(labyrinthMap, i, j + 1)){
                    return true;
                }
                // 再向上走
                else if (getWay(labyrinthMap, i - 1, j)){
                    return true;
                }
                // 再向左走
                else if (getWay(labyrinthMap, i, j - 1)){
                    return true;
                }else {
                    // 如果以上的所有方向读都不通，则说明这个点是走不通的
                    labyrinthMap[i][j] = 3;
                    return false;
                }
            }else {
                // labyrinthMap[i][j] != 0，则该点有 1，2，3 三种情况
                // 为1 是墙不同返回false
                // 为2 已经走过返回false
                // 为3 也同样是走不通
                return false;
            }
        }
    }
}
